package com.hatricks.is.base.sort;

import java.util.Arrays;

/**
 * @packageName: com.hatricks.base.sort
 * @className: QuickSort
 * @author: yanyuhui yanyuhui@chinasofti.com
 * @date: 2022/6/10 10:26
 * @description: 快速排序
 */
public class QuickSort {


    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 0, 1, 0, 3, -1, 23, -68, 7};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }

        // 1. 先声明基准值
        int pivot = arr[left];
        int l = left;
        int r = right;
        while (l < r) {
            while (l < r && arr[r] >= pivot) {
                r--;
            }
            while (l < r && arr[l] <= pivot) {
                l++;
            }
            // 尚未相遇 就碰见了 当前pivot不符合条件的值 进行值之间的交换
            if (l < r) {
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        // 将左边做小的值赋值给pivot 然后
        arr[left] = arr[l];
        arr[l] = pivot;
        if (left < l) {
            quickSort(arr, left, l - 1);
        }
        if (r < right) {
            quickSort(arr, r + 1, right);
        }

    }


}
